﻿// https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247489303&idx=2&sn=bacbc74296664edc8cb0491108ec42dd&scene=21#wechat_redirect
// https://leetcode-cn.com/problems/squares-of-a-sorted-array/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result, stack;
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            if (abs(nums[left]) >= abs(nums[right])) {
                stack.push_back(nums[left]*nums[left]);
                left++;
            } else if (abs(nums[left]) < abs(nums[right])) {
                stack.push_back(nums[right]*nums[right]);
                right--;
            }
        }

        while (stack.size()) {
            result.push_back(stack.back());
            stack.pop_back();
        }

        return result;
    }
};

int main() {
    Solution obj = Solution();
    vector<int> nums = {-4,-1,0,3,10};
    vector<int> aaa = obj.sortedSquares(nums);
    for (int i = 0; i < aaa.size(); i++)
        cout << aaa[i] << endl;
    
}


